
package com.liwt.offer.chapter2;

/**
 * <p>
 * 题目(剑指offer page55)：
 * <p>
 * 输入某二叉树的前序遍历和中序遍历结果，请重建二叉树。
 * <p>
 * 假设前序遍历和中序遍历中不含重复数字。
 * 
 * @author likebamboo
 */
public class ConstructeBinTree {

    /**
     * 构建二叉树
     * 
     * @param preOrder 先序遍历结果
     * @param inOrder 中序遍历结果
     * @return
     */
    private TreeNode constructeTree(int[] preOrder, int[] inOrder) {
        if (preOrder == null || inOrder == null || preOrder.length != inOrder.length) {
            return null;
        }
        return constructe(preOrder, 0, preOrder.length - 1, inOrder, 0, inOrder.length - 1);
    }

    /**
     * 构建二叉树的任意子树
     * 
     * @param preOrder 先序遍历结果
     * @param startPre 先序遍历开始位置
     * @param endPre 先序遍历结束位置
     * @param inOrder 中序遍历结果
     * @param startIn 中序遍历开始位置
     * @param endIn 中序遍历结束位置
     * @return
     */
    private TreeNode constructe(int[] preOrder, int startPre, int endPre, int[] inOrder,
            int startIn, int endIn) {
        if ((endPre - startPre) != (endIn - startIn)) {
            return null;
        }
        if (preOrder == null || inOrder == null || preOrder.length == 0 || inOrder.length == 0) {
            return null;
        }
        // 前序遍历的第一个节点为根节点
        int rootValue = preOrder[startPre];
        TreeNode root = new TreeNode();
        root.setValue(rootValue);

        // 只有一个元素，返回该节点
        if (startPre == endPre && startIn == endIn) {
            return root;
        }

        int rootIdx = -1, count = 0;
        // 遍历中序遍历结果，找到根节点的值
        for (int i = startIn; i <= endIn; ++i, ++count) {
            if (rootValue == inOrder[i]) {
                rootIdx = i;
                break;
            }
        }

        // 没有在中序遍历中找到该节点。
        if (rootIdx == -1) {
            return null;
        }

        if (count > 0) {
            // 构建左子树
            root.setLeftNode(constructe(preOrder, startPre + 1, startPre + count, inOrder, startIn,
                    rootIdx - 1));
        }

        if (endPre > startPre + count) {
            // 构建右子树
            root.setRightNode(constructe(preOrder, startPre + count + 1, endPre, inOrder,
                    rootIdx + 1, endIn));
        }
        return root;
    }

    public static void main(String[] args) {
        ConstructeBinTree binTree = new ConstructeBinTree();
        int[] preOrder1 = new int[] {
                1, 2, 4, 7, 3, 5, 6, 8
        };
        int[] inOrder1 = new int[] {
                4, 7, 2, 1, 5, 3, 8, 6
        };

        int[] preOrder2 = new int[] {
                1, 2, 4, 7, 3, 5, 6, 8
        };
        int[] inOrder2 = new int[] {
                8, 6, 5, 3, 7, 4, 2, 1
        };
        TreeNode root = binTree.constructeTree(preOrder1, inOrder1);
        System.out.println("普通二叉树 ，结果：" + root);
        root = binTree.constructeTree(preOrder2, inOrder2);
        System.out.println("只有左节点的二叉树 ，结果：" + root);
    }
}
